package com.suyl.mongodbdemo.BloomFilter;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class TestBloomFilter {
    private static final int DEFAULT_SIZE = (1 << 31) - 1; // m的值
    private static final int[] seeds = new int[]{9, 11, 13, 31, 37, 57}; // 6个函数
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private HashFunc[] func = new HashFunc[seeds.length];
    private static String words = "abcdefghijklmnopqrstuvwxyz1234567890_"; //

    public static void main(String[] args) {
        runFilter();
    }

    public static void runFilter() {
        TestBloomFilter filter = new TestBloomFilter();
        List<String> existList = new ArrayList<String>();
        List<String> noExistList = new ArrayList<String>();
        int countExist = 0;
        System.out.println("开始添加数据");
        int SampleCount = 100000000;
        for (int i = 0; i < SampleCount; i++) {
            String value = getStr();
            if (!filter.contains(value)) {
                if (existList.size() < 1000) {
                    existList.add(value);
                }
                filter.add(value);
            } else {
                countExist++;
            }
            if (i % 1000000 == 0) {
                System.out.println("已经添加:" + i);
            }
        }
        System.out.println("随机保存值重复了" + countExist);
        System.out.println(SampleCount + "比对样本值保存完毕");
        boolean flag = true;
        while (flag) {
            if (noExistList.size() > 999) {
                flag = false;
            } else {
                String str = getStr();
                if (!filter.contains(str)) {
                    noExistList.add(str);
                }
            }
        }
        System.out.println("1千的存在和不存在的待比对数据准备完毕");
        long start = System.currentTimeMillis();
        System.out.println("开始比对存在字符串");
        int existCount = 0;
        for (int i = 0; i < existList.size(); i++) {
            if (filter.contains(existList.get(i))) {
                existCount++;
            }
        }
        System.out.println("比对正确率:" + existCount + "/1000");
        System.out.println("开始比对不存在字符串");
        int noExistCount = 0;
        for (int i = 0; i < noExistList.size(); i++) {
            if (!filter.contains(noExistList.get(i))) {
                noExistCount++;
            }
        }
        System.out.println("比对正确率:" + noExistCount + "/1000");
        System.out.println("比对2千数据耗时：" + (System.currentTimeMillis() - start) + "毫秒");
        System.out.println("over");
    }

    /**
     * 获取随机比对字符串
     *
     * @return
     */
    public static String getStr() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 30; i++) {
            sb.append(words.charAt((int) (Math.random() * 37)));
        }
        sb.append(Math.random() * 100000);
        // sb.append(System.nanoTime());
        return sb.toString();
    }

    /**
     * 创建过滤器
     */
    public TestBloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new HashFunc(DEFAULT_SIZE, seeds[i]);
        }
    }

    /**
     * 添加样本数据
     *
     * @param value
     */
    public void add(String value) {
        for (HashFunc f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断是否存在
     *
     * @param value
     * @return
     */
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (HashFunc f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 哈希函数
     *
     * @author Administrator
     */
    public static class HashFunc {
        private int maxCount;
        private int seed;

        public HashFunc(int maxCount, int seed) {
            this.maxCount = maxCount;
            this.seed = seed;
        }

        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (maxCount - 1) & result;
        }
    }
}
